package com.ywgt;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int [] arr={125,26,266,15,0,124};
        quick(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quick(int [] arr,int left,int rigth){
        int l=left;   //左指针 负责找到左侧比mid大的数放到右指针下
        int r=rigth;    //右指针 负责找到右侧比mid小的数放到左指针下
        int mid=arr[(left+rigth)/2]; //定义mid数值大小
        int temp=0; //left right交换时的中间临时变量
        while (l<r){   //当了l<r时 说明此次的查找还没有完成 还没有扫描到mid下标位置
            while(arr[l]<mid){    //当左边的数比mid小时一直循环 直到找到比mid大的
                l+=1;
            }
            while(arr[r]>mid){   //当左边的数比mid大时一直循环 直到找到比mid小的
                r-=1;
            }
            if(l>=r){           //如果左边的下标大于等于右边的下标 证明本次循环结束 左侧都比Mid小 右边都比mid大
                break;
            }
            temp=arr[l];     //上面两个循环都结束后 可以交换一次位置
            arr[l]=arr[r];
            arr[r]=temp;
            if(arr[l]==mid){     //如果放到左边的的数和中间一样大，那么r的位置要前进一位
                r-=1;
            }
            if(arr[r]==mid){    //如果放到右边的数和中间一样大，那么l的位置要前进一位
                l+=1;
            }
        }
        if(l==r){    //当l==r时
            l+=1;
            r-=1;
        }
        if(left<r){  //如果右边的指针没有到达left位置说明左侧没有拆分排序完成，左侧递归
            quick(arr,left,r);
        }
        if(l<rigth){    //如果左边的指针没有到达right说明右侧没有拆分排序完成，进行右侧递归
            quick(arr,l,rigth);
        }
    }
}
